package com.bluebridgecup.BasicAlgorithms.BinarySearch;

import java.util.Scanner;

public class OrderedArrayQueryProcessor {
    static int[] a = new int[(int) 10e5];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取输入的数列长度n
        int n = in.nextInt();
        // 读取查询的次数q
        int q = in.nextInt();
        // 循环读取数列中的每个元素，存储到数组a中，数组下标从1开始
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        // 循环q次，处理每次查询
        while (q-- > 0) {
            // 读取查询类型
            int temp = in.nextInt();
            // 读取查询的左边界l
            int l = in.nextInt();
            // 读取查询的右边界r
            int r = in.nextInt();
            // 读取查询的目标值x
            int x = in.nextInt();
            // 调用check方法处理当前查询
            check(temp, l, r, x);
        }
        in.close();
    }

    static void check(int temp, int l, int r, int x) {
        switch (temp) {
            case 1:
                System.out.println(getL(a, l, r, x));
                break;
            case 2:
                System.out.println(getR(a, l, r, x));
                break;
            case 3:
                System.out.println(lower_bound(a, l, r, x));
                break;
            case 4:
                System.out.println(upper_bound(a, l, r, x));
                break;
        }
    }

    // 找到有序区间中等于x最左边的数字位置
    static int getL(int[] a, int l, int r, int x) {
        // 使用二分查找，当左边界小于右边界时继续循环
        while (l < r) {
            // 计算中间位置
            int mid = (l + r) >> 1;
            // 如果目标值x小于等于中间位置的值
            if (x <= a[mid]) {
                // 缩小右边界到mid位置
                r = mid;
            } else {
                // 否则，将左边界更新为mid+1
                l = mid + 1;
            }
        }
        // 如果最终位置的值不等于目标值x，返回-1表示未找到
        if (a[l] != x) return -1;
        // 返回找到的位置
        return l;
    }

    // 找到有序区间中等于x最右边的数字位置
    static int getR(int[] a, int l, int r, int x) {
        // 使用二分查找，当左边界小于右边界时继续循环
        while (l < r) {
            // 计算中间位置，这里加1是为了避免死循环
            int mid = (l + r + 1) >> 1;
            // 如果目标值x小于中间位置的值
            if (x < a[mid]) {
                r = mid - 1;
            } else {
                // 否则 将左边界更新为mid位置
                l = mid;
            }
        }
        // 如果最终位置的值不等于目标值x，返回-1表示未找到
        if (a[l] != x) return -1;
        // 返回找到的位置
        return l;
    }

    //找到有序区间中大于等于x第一个数字的位置
    static int lower_bound(int[] a, int l, int r, int x) {
        // 如果目标值x大于右边界的值，说明不存在大于等于x的元素，返回-1
        if (x > a[r]) return -1;
        // 使用二分查找，当左边界小于右边界时继续循环
        while (l < r) {
            // 计算中间位置
            int mid = (l + r) >> 1;
            // 如果目标值x小于等于中间位置的值
            if (x <= a[mid]) {
                // 缩小右边界到mid位置
                r = mid;
            } else {
                // 否则 将左边界更新为mid+1

            }
        }
        // 返回找到的位置
        return l;
    }

    // 找到有序区间中大于x第一个数字的位置
    static int upper_bound(int[] a, int l, int r, int x) {
        // 如果目标值x大于等于右边界的值，说明不存在大于x的元素，返回-1
        if (x >= a[r]) return -1;
        // 使用二分查找，当左边界小于右边界时继续循环
        while (l < r) {
            // 计算中间位置
            int mid = (l + r) >> 1;
            // 如果目标值x小于中间的值
            if (x < a[mid]) {
                // 缩小右边界到mid为止
                r = mid;
            } else {
                // 否则 将左边界更新为mid+1
                l = mid + 1;
            }
        }
        return l;
    }
}
